package 左哥算法.ch10暴力递归;

import org.junit.Test;

import java.util.Arrays;

public class Ch05鲍勃的生存点数 {

    /**
     * 三维转动态规划
     * 给你一个n*m的区域，你从 row，col位置出发，你必须走k步的情况下，你能存活的方式有多少种
     */
    @Test
    public void test(){
        int f1 = fun(5, 6, 3, 3, 3);
        System.out.println(f1);
        int f2 = dpFun(5, 6, 3, 3, 3);
        System.out.println(f2);
        compare();
    }
    public int fun(int n,int m,int row,int col,int k){
        if (row<=0||row>n||col<=0||col>m){  //未生还的情况
            return 0;
        }
        if (k==0){
            return 1;
        }
        return fun(n,m,row-1,col,k-1)   //向上走存活的情况
                +fun(n,m,row+1,col,k-1) //向下走
                +fun(n,m,row,col-1,k-1) //向左走
                +fun(n,m,row,col+1,k-1);//向右走
    }
    public int dpFun(int n,int m,int row,int col,int k){
        int[][][] dp=new int[k+1][n+2][m+2];    //多两个为了预防越界
        //basecase,剩0步时未越界的情况都为1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <=m; j++) {
                dp[0][i][j]=1;
            }
        }
        for (int z = 1; z < dp.length; z++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[z][i][j]+=dp[z-1][i-1][j];
                    dp[z][i][j]+=dp[z-1][i+1][j];
                    dp[z][i][j]+=dp[z-1][i][j-1];
                    dp[z][i][j]+=dp[z-1][i][j+1];
                }
            }
        }

        return dp[k][row][col];
    }
    public void compare(){
        int count=1000;
        while (count-- > 0) {
            int n= (int) (Math.random()*15+1);
            int m= (int) (Math.random()*15+1);
            int row= (int) (Math.random()*n+1);
            int col= (int) (Math.random()*m+1);
            int k= (int) (Math.random()*10+1);
            if (fun(n,m,row,col,k)!=fun(n,m,row,col,k)){
                System.out.println("存在错误");
            }
        }
    }
}
